Largest time for given digits [Brute Force]

Time: O(1); Space: O(1); easy

Given an array of 4 digits, return the largest 24 hour time that can be made. The smallest 24 hour time is 00:00, and the largest is 23:59. Starting from 00:00, a time is larger if more time has elapsed since midnight.

Return the answer as a string of length 5. If no valid time can be made, return an empty string.

Example 1:

Input: A = [1,2,3,4]

Output: “23:41”

Example 2:

Input: A = [5,5,5,5]

Output: “”

Notes:

• A.length == 4

• 0 <= A[i] <= 9

1. Brute Force

Intuition Try all possible times, and remember the largest one.

Algorithm For each possible ordering of the 4 digits, if it’s a legal time and the time is greater than the one we have stored, update the answer.

import itertools

class Solution1(object):
    """
    Brute Force
    """
    def largestTimeFromDigits(self, A):
        ans = -1
        for h1, h2, m1, m2 in itertools.permutations(A):
            hours = 10 * h1 + h2
            mins = 10 * m1 + m2
            time = 60 * hours + mins
            if 0 <= hours < 24 and 0 <= mins < 60 and time > ans:
                ans = time

        return "{:02}:{:02}".format(*divmod(ans, 60)) if ans >= 0 else ""

s = Solution1()
A = [1,2,3,4]
assert s.largestTimeFromDigits(A) == "23:41"
A = [5,5,5,5]
assert s.largestTimeFromDigits(A) == ""

import itertools

class Solution1a(object):
    """
    Brute Force
    """
    def largestTimeFromDigits(self, A):
        """
        :type A: List[int]
        :rtype: str
        """
        result = ""
        for i in range(len(A)):
            A[i] *= -1
        A.sort()
        for h1, h2, m1, m2 in itertools.permutations(A):
            hours = -(10*h1 + h2)
            mins = -(10*m1 + m2)
            if 0 <= hours < 24 and 0 <= mins < 60:
                result = "{:02}:{:02}".format(hours, mins)
                break
        return result

s = Solution1a()
A = [1,2,3,4]
assert s.largestTimeFromDigits(A) == "23:41"
A = [5,5,5,5]
assert s.largestTimeFromDigits(A) == ""

See also:

https://leetcode.com/problems/largest-time-for-given-digits